#include <iostream>
using namespace std;


// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};


class Solution {
public:
    Node* copyRandomList(Node* head) {
        // 如果头节点为空，直接返回空
        if (head == NULL)
        {
            return NULL;
        }
        // 添加一个头节点
        Node *h = new Node(-1);
        h->next = head;
        Node *p = h->next;
        // 建立双节点的单链表h
        while (p != NULL)
        {
            // 建立节点p的复制节点q
            Node *q = new Node(p->val);
            // 将节点q插入到节点p之后
            q->next = p->next;
            p->next = q;
            p = q->next;
        }
        // 节点指针向后面移动
        p = h->next;
        // 修改复制节点的random
        while (p != NULL)
        {
            if (p->random != NULL)
            {
                p->next->random = p->random->next;
            }
                            // p节点指针向后移动
                p = p->next->next;
            
        }
        Node *r = h;
        p = h->next;
        while (p != NULL)
        {
            // q指向复制的节点
            Node *q = p->next;
            // 删除节点q
            p->next = q->next;
            r->next = q;
            r = q;
            // 节点向后移动
            p = p->next;
        }
        r->next = NULL;
        // 将尾部节点的next滞空
        return h->next;
        
        
    }
};

int main(){

    return 0;
}